import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Gao zhao xu
 * Date: 2023-12-05
 * Time: 下午 04:07
 */
public class UnionFindSet {
    public int[] elem;
    public int usedSize;

    public UnionFindSet(int n) {
        this.usedSize = n;
        this.elem = new int[n];
        Arrays.fill(elem, -1);
    }

    /**
     * 查找数据x的根节点
     */
    public int findRoot(int x) {
        if (x < 0) throw new IndexOutOfBoundsException("下标不合法");
        while (elem[x] >= 0) x = elem[x];
        return x;
    }
    /**
     * 查询x1和x2是不是同一个集合
     */
    public boolean isSameSet(int x1, int x2) {
        int x1Root = findRoot(x1);
        int x2Root = findRoot(x2);
        return x1Root == x2Root;
    }

    /**
     * 合并x1和x2所在的集合
     * @param x1
     * @param x2
     */
    public void union(int x1, int x2) {
        int x1Root = findRoot(x1);
        int x2Root = findRoot(x2);
        if (x1Root != x2Root) {
            if (x1Root > x2Root) {
                int tmp = x1Root;
                x1Root = x2Root;
                x2Root = tmp;
            }
            elem[x1Root] += elem[x2Root];
            elem[x2Root] = x1Root;
        }
    }

    public int getSetsCount() {
        int count = 0;
        for (int x : elem) {
            if (x < 0) count++;
        }
        return count;
    }
    public void show() {
        for (int i = 0; i < usedSize; i++){
            System.out.print(i + "(" + elem[i] + ") ");
        }
        System.out.println();
    }
}
